package src.com.java.dtgh.threeDay;

import src.com.java.Util;

import java.util.Arrays;

public class demo4 {

    /**
     * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     *
     * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
     *
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     * @param strs
     * @param m
     * @param n
     * @return
     */

    public static void main(String[] args) {

        demo4 demo4 = new demo4();

        demo4.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"},5,3);
    }

    public int findMaxForm(String[] strs, int m, int n) {

        /**
         * 定义dp[j]
         * j为最多可以放多少个0
         * dp[j]为最多可以放j个0时最大得子集长度;
         */
        int len = strs.length;

        int[] zero = new int[len];
        int[] one = new int[len];

        check01(zero,one,strs);

        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
//        Arrays.fill(dp,0);
        for (int i = 0; i < dp.length; i++) {
            for (int i1 = 0; i1 < dp[0].length; i1++) {
                dp[i][i1] = 0;
            }
        }

        for(int i = 0;i < len;i++){

            for(int x = m;x >= zero[i];x--){
                for(int y = n;y >= one[i];y--){
                    dp[x][y] = Math.max(dp[x][y],dp[x-zero[i]][y-one[i]]+1);
                }
            }
        }

        return dp[m][n];

    }

    public int findMaxForm2(String[] strs, int m, int n) {

        /**
         * 定义dp[j]
         * j为最多可以放多少个0
         * dp[j]为最多可以放j个0时最大得子集长度;
         */
        int len = strs.length;

        int[] zero = new int[len];
        int[] one = new int[len];

        check01(zero,one,strs);

        int[] dp0 = new int[m + 1];
        int[] dp1 = new int[n + 1];
        Arrays.fill(dp0, 0);
        Arrays.fill(dp1, 0);

        for(int i = 0;i < len;i++){
            for(int j = m;j >= zero[i];j--){
                dp0[j] = Math.max(dp0[j],dp0[j - zero[i]] + 1);
            }
            for(int k = n;k >= one[i];k--){
                dp1[k] = Math.max(dp1[k],dp1[k - one[i]] + 1);
            }
        }

        return dp0[m] > dp1[n] ? dp1[n] : dp0[m];

    }

    public void check01(int[] zero,int[] one,String[] strs){

        for (int i = 0; i < strs.length; i++) {
            int m = 0;
            String s = strs[i];
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '0') {
                    m++;
                }
            }
            zero[i] = m;
            one[i] = s.length() - m;
        }

        Util.printArray(zero);
        Util.printArray(one);
    }
}
